package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;
import com.study.algorithm.utils.ListUtil;

import java.util.List;

import static com.study.algorithm.utils.ListUtil.ExchangeValue;


/**
 * 堆排序
 * 原理：（使用大顶堆为例实现由小到大排序）
 * 第一步初始化堆（无序）
 * 第二步调整堆得最大值到堆顶
 * 第三步交换堆顶与堆低元素
 * 第四部堆低坐标前移一位
 * 第五步，重复第二三四步，知道堆低坐标与堆顶坐标一致（最后得到的集合即为有序集合）
 */
public class HeapSortImpl implements BasicalSort {
    @Override
    public List<Integer> basicalSort(List<Integer> originList) {
        int size = originList.size();
        List<Integer> destList = ListUtil.DeepClone(originList);
        if (size <= 1) {
            return destList;
        }

        for (int endIndex = size - 1; endIndex > 0; endIndex--) {
            adjustMaxElementToTopNode(destList, endIndex);
            exchangeTopAndCurrBottomVal(destList, 0, endIndex);

        }
        return destList;
    }

    private void exchangeTopAndCurrBottomVal(List<Integer> list, int topIndex, int bottomIndex) {
        if (topIndex == bottomIndex) {
            return;
        }
        ExchangeValue(list, topIndex, bottomIndex);
    }

    private void adjustMaxElementToTopNode(List<Integer> list, int endIndex) {
        for (int currIndex = endIndex; currIndex > 0; currIndex -= 2) {
            adjustMaxElementToParentNode(list, currIndex, endIndex);
        }
    }

    private void adjustMaxElementToParentNode(List<Integer> list, int currIndex, int endIndex) {
        int parentIndex = getParentNodeIndex(currIndex);
        int brotherIndex = getBrotherNodeIndex(currIndex);
        boolean isHasBrother = brotherIndex <= endIndex;
        int currVal = list.get(currIndex);
        int parentVal = list.get(parentIndex);
        int brotherVal = isHasBrother ? list.get(brotherIndex) : -1;
        boolean isBiggerForBrotherVal = isHasBrother && currVal <= brotherVal;
        //上面一堆变量主要为了是能够区分每一步使用的变量含义，使其更容易阅读
        //逻辑就是下面两个if语句

        if (isBiggerForBrotherVal && parentVal < brotherVal) {
            ExchangeValue(list, brotherIndex, parentIndex);
        }
        if (!isBiggerForBrotherVal && parentVal < currVal) {
            ExchangeValue(list, currIndex, parentIndex);
        }
    }

    private int getParentNodeIndex(int currIndex) {
        //childNode值等于fatherNode*2+1或者father*2+2
        return (currIndex - 1) / 2;//向下取整
    }

    private int getBrotherNodeIndex(int currIndex) {
        // leftChildNode = fatherNode * 2 + 1
        //rightchildNode = fatherNode * 2 + 2
        boolean isRightBrotherNodeForCurrNode = (currIndex - 1) % 2 == 1;
        return isRightBrotherNodeForCurrNode ?
                currIndex - 1 : currIndex + 1;
    }

}
